package com.fang.sort;

import java.util.Comparator;

import com.fang.base.utils.SwapUtils;

/**
 * <p>
 * 算法描述
 * </p>
 * 
 * <p>
 * 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
 * </p>
 * <p>
 * 所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。
 * </p>
 * <p>
 * 取第二个增量d2 < d1重复上述的分组和排序，
 * </p>
 * <p>
 * 直至所取的增量dt=1(dt < dt-l < … < d2 < d1)，即所有记录放在同一组中进行直接插入排序为止。
 * </p>
 *
 * <p>
 * <b> 希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n^2)，而Hibbard增量的希尔排序的时间复杂度为O(N^(5/4))，
 * 但是现今仍然没有人能找出希尔排序的精确下界。</b>
 * </p>
 * 
 */
public class ShellSort {

	public static void main(String[] args) {
		Integer[] sort = { 2, 5, 45, 87, 1, 254, 58 };

		ShellSort shellSort = new ShellSort();
		Integer[] data = shellSort.sort2(sort, sort.length >> 1, new Comparator<Integer>() {
			@Override
			public int compare(Integer data1, Integer data2) {
				if (data1 < data2)
					return 1;
				if (data1 > data2)
					return -1;
				return 0;
			}
		});
		for (Integer integer : data) {
			System.out.print(integer + "   ");
		}
	}

	public <T> T[] sort(T[] data, int step, Comparator<? super T> comparator) {
		System.out.println(data + "  " + step);
		if (data == null || comparator == null)
			return data;
		for (int i = 0; i < step; i++) {
			for (int j = step + i; j < data.length; j = j + step) {
				for (int k = j; k >= step; k = k - step) {
					if (comparator.compare(data[k], data[k - step]) > 0) {
						SwapUtils.swap(data, k, k - step);
					} else {
						// 此时插入的数据已经到达正确位置
						break;
					}
				}
			}
		}
		if (step != 1) {
			sort(data, step >> 1, comparator);
		}
		return data;
	}

	public <T> T[] sort2(T[] data, int step, Comparator<? super T> comparator) {
		System.out.println(data + "  " + step);
		if (data == null || comparator == null)
			return data;
		for (int i = step; i < data.length; i++) {
			int index = i;
			while (index >= step)
				if (comparator.compare(data[index], data[index - step]) > 0) {
					SwapUtils.swap(data, index, index - step);
				} else {
					// 此时插入的数据已经到达正确位置
					break;
				}
		}
		if (step != 1) {
			sort(data, step >> 1, comparator);
		}
		return data;
	}

}
